package com.zhugang.week10;

/**
 * @program algorithms
 * @description: bages2ByBacktrack
 * @author: chanzhugang
 * @create: 2022/08/28 21:05
 */
public class Bages2ByBacktack {

    /**
     * 二维费用背包问题
     * 回溯解法： 无法用备忘录去重
     *
     * @param i
     * @param cw
     * @param cv
     */
    private int maxV = Integer.MIN_VALUE;
    private int[] items = {2, 2, 4, 6, 3};
    // 物品对应费用
    private int[] values = {3, 4, 8, 9, 6};
    // 物品个数
    private int n = 5;
    // 背包承受最大重量
    private int w = 9;

    public void f(int i, int cw, int cv) {
        if (cw == w || i == n) {
            // 装满了 或者 考察完了
            if (cv > maxV) {
                maxV = cv;
                return;
            }
        }
        f(i + 1, cw, cv);
        if (cw + items[i] <= w) {
            f(i + 1, cw + items[i], cv + values[i]);
        }
    }
}